#ifndef SPLAY_TREE_H
#define SPLAY_TREE_H

#include "dsexceptions.h"
#include <algorithm>
#include <iostream> 
using namespace std;

template <typename Comparable>
class SplayTree
{
    public:
    SplayTree()
    {   
        nullnode = new BinaryNode(0,NULL,NULL);
        nullnode->left = nullnode->right = nullnode;
 
        root = nullnode; //不赋值为0，则root值是随机数
    }   
 
    ~SplayTree(){};


    /**
     * Deep copy.
     */
    SplayTree & operator=( const SplayTree & rhs )
    {
        SplayTree copy = rhs;
        std::swap( *this, copy );
        return *this;
    }
        
    /**
     * Move.
     */
    SplayTree & operator=( SplayTree && rhs )
    {
        std::swap( root, rhs.root );
        return *this;
    }


    void insert(const Comparable& x)
    {   
        insert(x,root);         
    }   
 
    /**
     * Insert x into the tree; duplicates are ignored.
     */
    void insert( Comparable && x )
    {
        insert( std::move( x ), root );
    }

    void remove( const Comparable & x )
    {
        remove( x, root );
    }

    void printTree()
    {   
        printTree(root);        
    }   
 
    void splay(const Comparable& x)
    {   
        splay(x,root);
    }   

    void InorderTravesal(vector<Comparable> &ret)
    {
        if(this->root != nullptr)
            InorderHelper(ret, this->root);
        else
            std::cout<<"error size"<<endl;
    }
 
    private:
 
    typedef struct BinaryNode
    {
        Comparable element;
        struct BinaryNode * left;
        struct BinaryNode * right;
    
        BinaryNode(const Comparable& theElement, BinaryNode * lt,BinaryNode * rt):
            element(theElement),left(lt),right(rt){};
    }BinaryNode;
 
 
    BinaryNode * root;
    BinaryNode * nullnode;
 

     void InorderHelper(vector<Comparable> & ret, BinaryNode * root)
    {
        if(root == nullnode) return;
        InorderHelper(ret, root->left);
        ret.push_back(root->element);
        InorderHelper(ret,root->right);    
    }
 
    /* 
     *注释说明：
     * T 表示当前的根节点
     * p 表示当前根节点的孩子节点
     * x 表示待查找元素
     * */
    void splay(const Comparable& x, BinaryNode *& root)
    {
        static BinaryNode header(x,nullnode,nullnode);
        BinaryNode * leftTreeMax,*rightTreeMin;
        header.right = header.left = nullnode;   //因为static 语句只会调用一次对象的构造函数,所以必须要在这里清空左右子树
 
 
        leftTreeMax = rightTreeMin = &header;   
        
        nullnode->element = x;
 
 
        for(;;)
        {
            if(x < root->element)
            {
                BinaryNode * leftChild = root->left;
                
                if(x < leftChild->element)
                {
                    rotateWithLeftChild(root);  // 该函数执行完成后，root 指向p 节点
                }
 
 
                if(root->left == nullnode)      // nullnode 和 这个判断节点为空的语句是否应该在上面的 <span style="font-family: Arial, Helvetica, sans-serif;">if(x < leftChild->element) 判断语句之前再放一个的解释见注释7</span>
 
                    break;
 
 
                rightTreeMin->left = root;
                rightTreeMin = root;
 
                root = root->left;
                    
            }
            else if(x > root->element)
            {
                BinaryNode * rightChild = root->right;
                if(x > rightChild->element)
                {
                    rotateWithRightChild(root);     
                }
 
                if(root->right == nullnode)
                    break;
 
 
                leftTreeMax->right = root;
                leftTreeMax = root;
                
                root = root->right; 
            }
            else
                break;
        }
        
        leftTreeMax->right = root->left;
        rightTreeMin->left = root->right;
 
 
        root->left = header.right;
        root->right = header.left;
    }
 
    /*
     *             root            leftChild
     *              /                /  \
     *        leftChild  ==>      other root
     *           /   \                  /
     *         left right            right
     **/
    void rotateWithLeftChild(BinaryNode *& root)
    {
        BinaryNode * leftChild = root->left;
        root->left = leftChild->right;
        leftChild->right = root;
 
 
        root = leftChild;   
    }
 
 
    /*
     *             root            rightChild
     *               \                /  \
     *            rightChild        root  right
     *              /   \             \ 
     *            left right         left 
     **/
    void rotateWithRightChild(BinaryNode *& root)
    {
        BinaryNode * rightChild = root->right;
        root->right = rightChild->left;
        rightChild->left = root;
        
        root = rightChild;
    }
 
 
    void printTree(BinaryNode * node)
    {
        if(node == nullnode)
        {
            return;
        }
 
 
        cout << node->element << endl;
        printTree(node->left);
        printTree(node->right);
    } 
 
    void remove(const Comparable& x, BinaryNode *& root)
    {
        BinaryNode * newTree;
 
 
        //删除一个节点也要重新调整树的结构
        //因为伸展树可能极度不平衡，如果使用递归的方法来删除一个
        //节点，则在大数据中可能会导致栈溢出
        splay(x,root);
 
 
        if(x == root->element)
        {
            /* 
             * 如果左子树为空则右子树的根就是新树的根
             * 如果左子树不为空，则使用左子树最大的节点（最右节点）作为新树的根
             * */
            if(root->left == nullnode)
            {
                newTree = root->right;
            }
            else
            {
                newTree = root->left;
                /* 再次重构整个伸展树 */
                splay(x,newTree);  // 找到左子树最大的节点
                newTree->right = root->right;  //让左子树最大的节点作为新树的根
            }
            delete root;
            root = newTree;
        }
    }
 
    void insert(const Comparable& x,BinaryNode *& root)
    {
        static BinaryNode * newNode = NULL;
        if(newNode == NULL)
        {
            newNode = new BinaryNode(x,nullnode,nullnode);  
        }
        newNode->element = x;
 
 
        if(root == nullnode)
        {
            root = newNode;
            root->left = root->right = nullnode;
        }
        else
        {
            splay(x,root);
            if(x < root->element)
                {
                    newNode->left = root->left;  //splay 完成后，根据伸展规则root的左子树都小于关键字
                    newNode->right = root;        // root 的右子树都大于关键字,所以要把左子树的元素挂在到
                                                //新节点的左子树上，而root和root的右子树都大于关键字  ，见注释8
                    root->left = nullnode;       //保证所有的空节点都指向nullnode
                    root = newNode;              //新插入的节点作为root节点
                }
            else if(x > root->element)
            {
                newNode->right = root->right;
                newNode->left = root;
 
 
                root->right = nullnode;
                root = newNode;
            }
            else
                return;  // 查到重复元素，则此次new的BinaryNode没有使用，所以下一次插入新的节点时，可以不用重新new
        }          
        newNode = NULL;
    }
};
#endif